package com.lry.basic.algorithm.bit;


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class BitMaps {

    private Map<String, Byte[]> map = new HashMap<>();


    /**
     * 零存：setbit key offset value
     * @param key 键
     * @param offset 0~7拿第一个字节，8~15拿第二个字节
     * @param value 0 or 1
     * @return
     */
    public boolean setBit(String key,int offset,String value){
        checkKey(key);
        checkKey(value);
        checkOffset(offset);
        //如果map.get是null，则new一个
        Byte[] bytes  = map.computeIfAbsent(key, k -> new Byte[1]);
        int i = offset/8;
        int pos = offset%8;
        int num = 0;
        //是否需要扩容
        if(bytes.length<i+1){
            //扩容
            bytes = Arrays.copyOf(bytes,i+1);
        }
        if(bytes[i]!=null){
            num = bytes[i];
        }

        if(value.equals("0")){
            num = FD_CLR(pos,num);
        }else{
            num = FD_SET(pos,num);
        }
        bytes[i] = (byte)num;
        map.put(key,bytes);
        return true;
    }

    /**
     * offset处是否置位1
     * gitbit key offset
     * @param key
     * @param offset
     * @return
     */
    public boolean getBit(String key,int offset){
        checkKey(key);
        checkOffset(offset);
        Byte[] bytes = map.get(key);
        int i = offset/8;

        if(null==bytes||bytes.length==0||i>=bytes.length||null==bytes[i])
            return false;

        int pos = offset%8;
        return FD_ISSET(pos,bytes[i]);
    }

    /**
     * 统计第start个字节到end个字节一共有多少位 置1
     * @param key
     * @param start
     * @param end
     * @return
     */
    public int bitCount(String key,int start,int end) {
        checkKey(key);
        if (start > end||start<0||end<0)
            throw new RuntimeException("不符合规则：end>=start,start>=0,end>=0");
        Byte[] bytes = map.get(key);
        if (null == bytes || bytes.length == 0)
            return 0;

        int count = 0;
        for(int i=start;i<=end&&i<bytes.length;i++){
            if(null!=bytes[i])
                count+=countBit(bytes[i]);
        }
        return count;
    }

    /**
     * 统计第start个位到end个位一共有多少位 置1
     * @param key
     * @param start
     * @param end
     * @return
     */
    public int bitCountByBit(String key,int start,int end){
        checkKey(key);
        if (start > end||start<0||end<0)
            throw new RuntimeException("不符合规则：end>=start,start>=0,end>=0");
        Byte[] bytes = map.get(key);
        if (null == bytes || bytes.length == 0)
            return 0;

        int count = 0;
        //start=1,end=20
        //i=0,posI=1
        //j=2,posJ=4
        //统计第第一个字节的1，2，3，4，5，6，7位+第二个字节+第三个字节的0，1，2，3，4

        int i = start/8;
        int posI = start%8;
        if(posI!=0){
            //左边部分posI~7
            if(null!=bytes[i]){
                for(int p=posI;p<=7;p++){
                    if(FD_ISSET(p,bytes[i]))
                        count++;
                }
            }
            i = i+1;
        }

        int j = end/8;
        int posJ = end%8;
        if(posJ!=7){
            //右边部分0~posJ
            if(null!=bytes[j]){
                for(int p=0;p<=posJ;p++){
                    if(FD_ISSET(p,bytes[j]))
                        count++;
                }
            }
            j = j-1;
        }


        //中间部分计算
        for(int k=i;k<=j&&k<bytes.length;k++){
            if(bytes[k]!=null)
                count+=countBit(bytes[k]);
        }


        return count;
    }

    /**
     * 返回置位1的最小下标
     * @param key
     * @return
     */
    public int bitPos(String key){
        checkKey(key);
        Byte[] bytes = map.get(key);
        if(null==bytes||bytes.length==0)
            return -1;

        int index =0;
        for(int i=0;i<bytes.length;i++){
            if(bytes[i]!=null){
                index+=i*8;
                for(int p=0;p<7;p++){
                    if(FD_ISSET(p,bytes[i])){
                        index+=p;
                        break;
                    }
                }
                break;
            }
        }
        return index;
    }

    public int bitCount(String key){
        checkKey(key);
        Byte[] bytes = map.get(key);
        if(null==bytes||bytes.length==0)
            return 0;
        int count = 0;
        for(Byte num:bytes){
            if(null!=num)
                count+=countBit(num);
        }
        return count;
    }


    private int countBit(byte num){
        int count = 0;
        while(num>0){
            count++;
            num = (byte) (num&(num-1));
        }
        return count;
    }

    private boolean FD_ISSET(int pos,int num){
        return (num&((1<<pos)))!=0;
    }

    private int FD_SET(int pos,int num){
        return num |= (1<<pos);
    }

    private int FD_CLR(int pos,int num){
        return  num &= ~(1<<pos);
    }

    private void checkOffset(int offset){
        if(offset<0)
            throw new RuntimeException("offset is invalid");
    }

    private void checkKey(String key){
        if(isEmpty(key))
            throw new RuntimeException("key is invalid");
    }
    private void checkValue(String value){
        if(isEmpty(value))
            throw new RuntimeException("value is invalid");
        if(!value.equals("0")&&!value.equals("1"))
            throw new RuntimeException("value must be 0 or 1");
    }

    private boolean isEmpty(String str){
        if(null==str||str.length()==0)
            return true;
        return false;
    }



}
